package Algorithm.Linked;

/**
 * @author chenjunjie
 * @since 2018-04-25
 */
public class LinkedListImpl implements LinkedListDemo {
    private LinkNoed first;
    private LinkNoed last;
    private int size;


    @Override
    public void add(int data) {
        linkLast(data);
    }

    @Override
    public void add(int e, int index) {
        if (index == size) {
            linkLast(e);
        }else {
            linkBefore(e, getNode(index));
        }
    }

    @Override
    public void removeFirst() {

    }

    @Override
    public int remove(int index) {
        return 0;
    }

    @Override
    public int removeLast() {
        return 0;
    }


    @Override
    public int getFirst() {
        return first.item;
    }

    @Override
    public int getLast() {
        return last.item;
    }

    @Override
    public int get(int index) {
        return getNode(index).item;
    }

    @Override
    public int getSize(){
        return size;
    }

    /**
     * 获取指定位置的节点信息
     * @param index
     * @return node
     */
    public LinkNoed getNode(int index){
        // 分为两个方向遍历，提高效率
        if (index < (size >> 1)) {
            LinkNoed x = first;
            // 从前往后循环，到index位置就结束
            for (int i = 0; i < index; i++) {
                x = x.next;
            }
            return x;
        } else {
            LinkNoed x = last;
            // 从后往前循环，到index位置就结束
            for (int i = size - 1; i > index; i--) {
                x = x.prev;
            }
            return x;
        }

    }

    public void addLast(int data) {
        linkLast(data);
    }

    public void addFrist(int data) {
        linkFirst(data);
    }

    private void linkBefore(int data ,LinkNoed node){
        if(node == first){
            linkFirst(data);
            return;
        }
        if(node == last){
            linkLast(data);
            return;
        }

        final LinkNoed newNode = new LinkNoed(node.prev, data, node);
        node.prev.next = newNode;
        node.prev = newNode;
        size++;
    }

    private void linkLast(int data) {
        final LinkNoed l = last;
        final LinkNoed newNode = new LinkNoed(l, data, null);
        last = newNode;
        if (l == null){
            first = newNode;
        }else{
            l.next = newNode;
        }

        this.size++;
    }

    private void linkFirst(int e) {
        final LinkNoed f = first;
        final LinkNoed newNode = new LinkNoed(null, e, f);
        first = newNode;
        if (f == null) {
            last = newNode;
        }else {
            f.prev = newNode;
        }
        this.size++;
    }


}
